
//934.最短的桥
class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        //将水面填平,让两座岛形成一座岛
        //可以让一座岛向外进行扩展,当从一座岛扩展到另一座岛的时候,其就已经填平了,直接返回扩展的次数即可
        int n=grid.size(),m=grid[0].size();
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};

        //先分别对两座岛的陆地进行统计
        function<void(queue<pair<int,int>>&,int,int)> dfs=[&](queue<pair<int,int>>& q,int x,int y)
        {
            grid[x][y]=2;   //将这个岛置为2,于另一个岛进行区分
            q.push({x,y});
            for(int k=0;k<4;k++)
            {
                int a=x+dx[k],b=y+dy[k];
                if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) dfs(q,a,b);
            }
        };

        queue<pair<int,int>> q;
        int flag=1;
        for(int i=0;i<n&&flag;i++)
        {
            for(int j=0;j<m&&flag;j++)
            {
                if(grid[i][j]==1)
                {
                    dfs(q,i,j);
                    flag=0;  //通过flag标记来跳出循环
                }
            }
        }

        //此时一个岛都已经进行统计了
        //让这个岛向外进行扩展,直到扩展到另一个岛
        int step=0;  //记录已经扩展的次数
        while(q.size())
        {
            int _size=q.size();
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) return step;
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==0) 
                    {
                        grid[a][b]=2;
                        q.push({a,b});
                    }
                }
            }
            step++;
        }
        return -1;
    }
};